package org.lql.algo.codecrush.week006;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:53
 * @description: LCR 170. 交易逆序对的总数 <a href="https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/">...</a>
 **/
public class ReversePairs {

	/**
	 * 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。
	 * 请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：record = [9, 7, 5, 4, 6]
	 * 输出：8
	 * 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * 0 <= record.length <= 50000
	 */
	public int reversePairs(int[] record) {
		if (record == null || record.length <= 1) {
			return 0;
		}
		int[] temp = new int[record.length];
		return (int) mergeSort(record, temp, 0, record.length - 1);
	}

	private long mergeSort(int[] arr, int[] temp, int left, int right) {
		if (left >= right) return 0;
		int mid = left + (right - left) / 2;
		long count = 0;
		count += mergeSort(arr, temp, left, mid);
		count += mergeSort(arr, temp, mid + 1, right);

		// 若本层已整体有序，跳过归并
		if (arr[mid] <= arr[mid + 1]) return count;

		count += merge(arr, temp, left, mid, right);
		return count;
	}

	private long merge(int[] arr, int[] temp, int left, int mid, int right) {
		for (int i = left; i <= right; i++) {
			temp[i] = arr[i];
		}
		int i = left, j = mid + 1;
		long count = 0;

		for (int k = left; k <= right; k++) {
			if (i > mid) {
				arr[k] = temp[j++];
			} else if (j > right) {
				arr[k] = temp[i++];
			} else if (temp[i] <= temp[j]) { // 相等不计入逆序对
				arr[k] = temp[i++];
			} else {
				arr[k] = temp[j++];
				count += (mid - i + 1); // 左侧剩余元素都大于 temp[j-1]
			}
		}
		return count;
	}

	public static void main(String[] args) {
		ReversePairs reversePairs = new ReversePairs();
		int[] record = {9, 7, 5, 4, 6};
		int count = reversePairs.reversePairs(record);
		System.out.println(count);
	}
}
